Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Tree View Pattern (medium)
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Comparison of Two Trees Pattern (medium)
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Subtree of Another Tree

Problem Statement

Given the roots of two binary trees, root and subRoot, return true if subRoot is a subtree of root. Otherwise, return false.

A subtree of a binary tree is a part of the tree that includes a node and all of its descendants. The tree tree could also be considered as a subtree of itself.

Examples

Example 1

  • Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]
Image
  • Expected Output: true
  • Explanation: The subtree starting at node 6 in root has the same structure and values as subRoot.

Example 2

  • Input: root = [3, 4, 5, null, 2, null, 1], subRoot = [4, null, 2]
Image
  • Expected Output: true
  • Explanation: The subtree rooted at node 4 in root matches the structure and values of subRoot.

Example 3

  • Input: root = [3, 4, 5, 1, 2, null, null, 0], subRoot = [4, 1, 2]
Image
  • Expected Output: false
  • Explanation: While node 4 exists in root, its subtree structure is different because of the extra node 0.

Constraints:

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

Solution

In this problem, the goal is to check whether subRoot is a subtree of root. We use a recursive algorithm that traverses the entire root tree, comparing each node's subtree with subRoot. The algorithm checks if the trees rooted at the current node of root and subRoot are identical. If they are, the function returns true. If not, the algorithm recursively checks the left and right subtrees of root. This method ensures that all possible subtrees of root are examined to see if they match subRoot.

We use a helper function to compare two trees. It determines if both trees have the same structure and node values. It recursively checks the left and right children of both trees. The algorithm relies on this helper function to determine if two trees are identical. If at any point the current subtree of root matches subRoot, we return true, otherwise, we continue searching the rest of root.

Step-by-step Algorithm

  1. Base Case: Check if subRoot is null:

    • If subRoot is null, return true. This is because an empty tree is always a subtree of any tree.
  2. Base Case: Check if root is null:

    • If root is null and subRoot is not null, return false. This is because a non-empty tree cannot be a subtree of an empty tree.
  3. Check if the current subtree rooted at root matches subRoot:

    • Call the helper function isSameTree(root, subRoot) to check if the subtree rooted at the current node of root is identical to subRoot. This comparison involves:
      • If both nodes are null, return true (both are identical).
      • If one of the nodes is null and the other is not, return false (they cannot be identical).
      • If the values of the current nodes are different, return false (the trees cannot be identical).
      • If the values of the current nodes are the same, recursively check if the left and right subtrees of both trees are identical by calling isSameTree on their respective left and right children.
  4. Recursively check the left and right subtrees of root:

    • If the current subtree rooted at root does not match subRoot, recursively call isSubtree(root.left, subRoot) and isSubtree(root.right, subRoot) to check the left and right subtrees of root.
  5. Return the result:

    • If at any point the trees match, return true. If no subtree matches subRoot, return false.

Algorithm Walkthrough

Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]):

  1. Starting at the root node of root (node 3):

    • Current Node in root: 3
    • Comparing with subRoot (node 6):
      • Node values are different (3 != 6), so we move forward to check the left and right subtrees of root.
  2. Checking the left subtree of root:

    • Current Node in root: 6 (left child of node 3)

    • Comparing with subRoot (node 6):

      • Node values are the same (6 == 6), so we now check the left and right subtrees of this node to see if they also match.
    • Comparing the left subtrees of node 6 in root and subRoot:

      • Left child of node 6 in root: 1
      • Left child of node 6 in subRoot: 1
      • Comparison:
        • Node values are the same (1 == 1), and both nodes have no further children (both left and right children are null).
      • Result: The left subtrees are identical.
    • Comparing the right subtrees of node 6 in root and subRoot:

      • Right child of node 6 in root: 4
      • Right child of node 6 in subRoot: 4
      • Comparison:
        • Node values are the same (4 == 4), and both nodes have no further children (both left and right children are null).
      • Result: The right subtrees are identical.
  3. Conclusion

    • Since both the left and right subtrees of node 6 in root match those in subRoot, the trees are identical.
    • The helper function isSameTree(root, subRoot) returns true.
  4. Final Step

    • The isSubtree function also returns true, confirming that subRoot is indeed a subtree of root.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • In the worst case, for every node in the root tree, we call the isSameTree() method to compare it with the subRoot. This results in a time complexity of , where:
    • n is the number of nodes in the root tree.
    • m is the number of nodes in the subRoot tree.
  • The isSameTree() method itself takes time as it compares all nodes in subRoot with the corresponding nodes in root.
  • Therefore, the overall time complexity is .

Space Complexity

  • The space complexity is determined by the depth of the recursion, which depends on the height of the trees.
  • In the worst case (for a completely unbalanced tree), the height of the tree could be for root and for subRoot.
  • Thus, the space complexity is , where h1 and h2 are the heights of the root and subRoot trees, respectively. In the worst case, this could be if both trees are skewed.

An Alternate Approach Using Tree Hash

In the first approach, the time complexity was , where N is the number of nodes in root and M is the number of nodes in subRoot. To optimize this, we use a hashing-based approach.

In this approach, we calculate the hash value for each subtree in root and store it. Then, we calculate the hash for subRoot and compare it with the stored hashes from root. If a match is found, we can immediately conclude that subRoot is a subtree of root. This optimization reduces the comparison time and improves efficiency by leveraging hashing techniques.

The overall approach is efficient because:

  • Instead of comparing entire subtrees at each node, we convert subtrees into hashes, reducing the need for full comparisons.
  • We use two prime numbers to generate unique hashes, minimizing the chances of collisions and ensuring correctness.

Step-by-step Algorithm

  1. Initialize constants and data structures:

    • Set two prime constants MOD_PRIME_1 and MOD_PRIME_2 for hashing to minimize hash collisions.
    • Create a list hashStore to store the hashes of all subtrees in root.
  2. Define the calculateHashForSubtree function:

    • Base Case: If the current node is null, return a default hash value {3, 7} to handle empty subtrees. Here, you can return any pair of prime numbers.

    • Recursively calculate the hashes for the left and right subtrees of the current node by calling calculateHashForSubtree on both.

    • Hash Calculation For the First Hash of the Pair:

      • Left Shift the Left Subtree Hash: Take the first hash of the left subtree and left shift it by a fixed value (e.g., 5). This gives more weight to the left subtree.

      • Left Shift the Right Subtree Hash: Take the first hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with slightly less weight.

      • Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value. This combines the contributions of the subtrees and the current node.

      • Take MOD_1: Apply MOD_PRIME_1 to the result to avoid overflow and keep the hash value within a manageable range.

    • Hash Calculation For the Second Hash of the Pair:

      • Left Shift the Left Subtree Hash: Take the second hash of the left subtree and left shift it by a different fixed value (e.g., 7). This gives a different weight to the left subtree for the second hash.

      • Left Shift the Right Subtree Hash: Take the second hash of the right subtree and left shift it by 1 (or another fixed value). This adds the right subtree’s contribution with a slight weight.

      • Add Node’s Value: Add the shifted values of the left and right subtree hashes to the current node's value to compute the second part of the hash.

      • Take MOD_2: Apply MOD_PRIME_2 to the result to avoid overflow and ensure the second hash value remains within the bounds of the prime.

  3. Hash all subtrees in root:

    • Call calculateHashForSubtree(root, true) to compute and store the hashes of all subtrees in root.
  4. Hash the subRoot tree:

    • Call calculateHashForSubtree(subRoot, false) to compute the hash for subRoot. We do not store this hash.
  5. Compare the subRoot hash with stored hashes:

    • Loop through the hashStore list and compare the hash of subRoot with each stored hash.
    • If a match is found (both hash parts are equal), return true because subRoot is a subtree of root.
  6. Return false if no match is found:

    • If no matching hash is found in hashStore, return false as subRoot is not a subtree of root.

Algorithm Walkthrough

Input: root = [3, 6, 5, 1, 4], subRoot = [6, 1, 4]

  1. Step 1: Initialize Constants and Data Structures:

    • Initialize MOD_PRIME_1 = 1000000007 and MOD_PRIME_2 = 2147483647.
    • Initialize an empty list hashStore to store hashes of subtrees.
  2. Step 2: Compute Hash for root:

    • Start at the root node of root (node 3).
    • Call calculateHashForSubtree on node 3:
      • Compute hashes for left and right subtrees of node 3.

    Left Subtree of Node 3:

    • Node 3's left child is node 6.

    • Call calculateHashForSubtree on node 6:

      • Compute hashes for left and right subtrees of node 6.

      Left Subtree of Node 6:

      • Node 6's left child is node 1.
      • Node 1 has no children, so return default hash {3, 7} for both left and right children.
      • Compute the hash for node 1 using the left and right subtree hashes:
        • Hash for node 1: ( (3 << 5) + (3 << 1) + 1 ) % MOD_PRIME_1 = 101, ( (7 << 7) + (7 << 1) + 1 ) % MOD_PRIME_2 = 897.
      • Store this hash {101, 897} in hashStore.

      Right Subtree of Node 6:

      • Node 6's right child is node 4.
      • Node 4 has no children, so return default hash {3, 7} for both left and right children.
      • Compute the hash for node 4 using the left and right subtree hashes:
        • Hash for node 4: ( (3 << 5) + (3 << 1) + 4 ) % MOD_PRIME_1 = 104, ( (7 << 7) + (7 << 1) + 4 ) % MOD_PRIME_2 = 900.
      • Store this hash {104, 900} in hashStore.
    • Compute the hash for node 6 using the left and right subtree hashes (hashes of nodes 1 and 4):

      • Hash for node 6: ( (101 << 5) + (104 << 1) + 6 ) % MOD_PRIME_1 = 3338, ( (897 << 7) + (900 << 1) + 6 ) % MOD_PRIME_2 = 115841.
      • Store this hash {3338, 115841} in hashStore.

    Right Subtree of Node 3:

    • Node 3's right child is node 5.

    • Node 5 has no children, so return default hash {3, 7} for both left and right children.

    • Compute the hash for node 5:

      • Hash for node 5: ( (3 << 5) + (3 << 1) + 5 ) % MOD_PRIME_1 = 105, ( (7 << 7) + (7 << 1) + 5 ) % MOD_PRIME_2 = 901.
      • Store this hash {105, 901} in hashStore.
    • Compute the hash for node 3 using the left and right subtree hashes (hashes of nodes 6 and 5):

      • Hash for node 3: ( (3338 << 5) + (105 << 1) + 3 ) % MOD_PRIME_1 = 107899, ( (115841 << 7) + (901 << 1) + 3 ) % MOD_PRIME_2 = 14826435.
      • Store this hash {107899, 14826435} in hashStore.
  3. Step 3: Compute Hash for subRoot:

    • Call calculateHashForSubtree on subRoot (node 6):
      • The process is the same as when we computed the hash for the left subtree of node 3 in root.
      • Hash for subRoot: {3338, 115841}.
  4. Step 4: Compare Hashes:

    • Loop through hashStore and check if any hash matches {3338, 115841} (the hash of subRoot).
    • A match is found in hashStore, confirming that subRoot is a subtree of root.
  5. Step 5: Return true:

    • Since a matching hash was found, return true.

Code

Java

. . . .

Complexity Analysis

Time Complexity

  • n is the number of nodes in the root tree, and m is the number of nodes in subRoot.
  • We traverse each node in both root and subRoot trees to compute their hash values. This takes for root and for subRoot.
  • After computing the hashes, we compare the hash of subRoot with all stored hashes from root, which takes . Thus, the total time complexity is .

Space Complexity

  • We store the hashes of all subtrees in root, which requires space.
  • Additionally, the recursive depth (call stack) for the calculateHashForSubtree function depends on the height of the trees, which is for root and for subRoot. Therefore, the total space complexity is .
Subtree of Another Tree (easy)
Isomorphic Trees (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

An Alternate Approach Using Tree Hash

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity